package com.ww.springboot.boot.algorithm.leetcode2;

import java.util.HashMap;
import java.util.Map;

/**
 * 描述：
 *
 * @author 🧑 ‍wanwei
 * @since 2025-06-03 09:19
 */
public class B2364统计坏数对的数目 {

    public static void main(String[] args) {

        int[] nums = {43,69,66,40,33};
        //System.out.println(new B2364统计坏数对的数目().countBadPairs(nums));
        System.out.println(new B2364统计坏数对的数目().countBadPairs2(nums));
    }

    /**
     * 时间复杂度 O(nLogn)
     * 空间复杂度 O(1)
     * @param nums
     * @return
     */
    public long countBadPairs(int[] nums) {
        long count = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] - nums[i] != j - i) {
                    count++;
                }
            }
        }
        return count;
    }

    /**
     * 时间复杂度 O(n)
     * 空间复杂度 O(n)
     * @param nums
     * @return
     */
    public long countBadPairs2(int[] nums) {
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int n = nums[i] - i;
            map.computeIfPresent(n, (k,v) -> v + 1);
            map.putIfAbsent(n, 1);
        }
        Long l = 0L;
        //求组合数
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            l+= combination(entry.getValue());
        }
        return combination(nums.length) - l;
    }

    public long combination(int n) {
        if(n == 1){
            return 0;
        }
        if(n == 2){
            return 1;
        }
        return combination(n - 1) + (n-1);
    }
}
